#pragma once


/*
	child:				the first child of the node, nullptr if doesn't exist
	parent:				the parent of the node, nullptr if doesn't exist
	next:				the cousion of the node, nullptr if doesn't exist
	visit:				total simulation times
	win:				total win times
	lose:				total lose times
	ucb:				the remedy value of rate
	rate:				the rate of winning
						if the rival choose to drop this way, the rate of his winning
	chess_x:			current board state
	chess_o:			current board state
	move:				current board state
*/
struct node
{
	node * child;
	node * parent;
	node * next;
	int visit;
	int win;
	int lose;
	double ucb;
	double rate;

	int chess_x;
	int chess_o;
	int move;
};



// the maximun simulate times of a node
const int MAX_SIMULATE = 6000;

// the minimum simulate times of a node
const int MIN_SIMULATE = 5000;

// the maximum time of simulating
const int TIME_LIMIT = 10;



/*
	chess_x:	[in]	x position
	chess_o:	[in]	o position
	move:		[in]	currently, who is to move next
	simTimes:	[out]	total simulation times
	winTimes:	[out]	total win times
	rate:		[out]	win rate

	return value:		who wins (0 or 1)
*/
//int simulate(int chess_x, int chess_o, int move, int * simTimes = nullptr, int * winTimes = nullptr, double * rate = nullptr);


/*
	function:			simulate current game state with MonteCarlo Method
						for just once

	chess_x:	[in]	x position
	chess_o:	[in]	o position
	move:		[in]	currently, who is to move next

	return value:		who wins (0 or 1)
*/
int simulateOnce(int chess_x, int chess_o, int move);


/*
	function:			simulate multiple times with uct algorithm

	root:		[in]	the root node you want to simulate
*/
void uct(node * root);


/*
	function:			find a node in the same layer whose UCB is the maximum

	startNode:	[in]	the first node in the target layer

	return value:		a pointer to the node that has the max UCB value
*/
//node * findMaxUCBNode(node * startNode);


/*
	function:			find a node in the same layer whose UCB is the maximum

	parent:		[in]	the parent of the taget layer's node

	return value:		a pointer to the node that has the max UCB value
						nullptr if there is no child
*/
node * findMaxUCBNodeII(node * parent);


/*
	function:			find a node in the same layer whose UCB is the minimun

	parent:		[in]	the parent of the taget layer's node

	return value:		a pointer to the node that has the min UCB value
	nullptr if there is no child
*/
node * findMinUCBNodeII(node * parent);


/*
	function:			generate a new memory that stores a new node

	return value:		a pointer to that newly generated node
*/
inline node * generateNewNode()
{
	return (node *)malloc(sizeof(node));
}


/*
	function:			free the memory of the node and it's children

	n:			[in]	the node you want to free the memory
*/
void freeNodeMemory(node * n);


/*
	function:			free the memory of the node

	n:			[in]	the node you want to free the memory
*/
void freeNodeMemoryII(node * n);


/*
	function:			merge the state of the two player to one

	chess_x:	[in]	x position
	chess_o:	[in]	o position

	return value:		the merged board
*/
inline int mergeState(int chess_x, int chess_o)
{
	return chess_x | chess_o;
}


/*
	function:			initialize a newly generated node

	n:			[in]	the newly generated node
*/
inline void initializeNode(node * n)
{
	n->chess_o = 0;
	n->chess_x = 0;
	n->child = nullptr;
	n->move = 0;
	n->next = nullptr;
	n->parent = nullptr;
	n->rate = 0;
	n->ucb = INF;
	n->visit = 0;
	n->win = 0;
	n->lose = 0;
}


/*
	function:			determine whether a game state is game over

	chess_x:	[in]	x position
	chess_o:	[in]	o_position
*/
inline bool gameOver(int chess_x, int chess_o);


/*
	function:			get the other player

	player:		[in]	the player you want to get the other from
*/
inline int getTheOtherPlayer(int player)
{
	return 1 - player;
}


/*
	function:			get the winning player, -1 if the game is over but no one wins

	chess_x:	[in]	x position
	chess_o:	[in]	o position
*/
inline int getWinningPlayer(int chess_x, int chess_y);


/*
	function:			get the compensate value of node, using the UCT algorithm

	n:			[in]	the node you want to get the compensate value
*/
inline double getRemedyValue(node * n)
{
	return sqrt(2 * UCB_K * log(n->parent->visit) / n->visit);
}


/*
	function:			update the simulate result to root node

	n:			[in]	the node currently simulated
	winPlayer:	[in]	simulation result
*/
void traceBack(node * n, int winPlayer);


/*
	function:			for one round of simulation
						get the next node to be simulated
						if no node is to be simulated, return nullptr

	root:		[in]	the root node of the simulation

	return value:		the next node to be simulated, nullptr if doesn't exist

	note:				assume that the game state represented by root is not game over
*/
node * getNextSimulationNode(node * root);


/*
	function:			a node has been simulated too nuch time, need to be expanded,
						generate valid move, create node and attach them to root

	root:		[in]	the root node you want to expand nodes
*/
void generateChildren(node * root);


/*
	function:			given a game state, generate a random valid move, represented by binary

	chess_x:	[in]	x position
	chess_o:	[in]	o position
*/
int generateRandomMove(int chess_x, int chess_o);


/*
	function:			when UCT algorithm is applied, find the optimal move

	parent:		[in]	root node of the UCT algprithm
*/
node * findOptimalNode(node * parent);



void myDummyAlg(node * root);